package real.unknown.string;
import java.util.*;
public class StringDistance {
    static class Solution {
        /**
         * 将其中一个的一个字符全部改变为另一个后，两者之间的不同字符数量 xxxxx错误
         * 真实： 只能将S1变换某个字母
         * 
         * 
         * 计算最少的距离
         * @param S1 string字符串 第一个字符串
         * @param S2 string字符串 第二个字符串
         * @return int整型
         */
        public int GetMinDistance1 (String S1, String S2) {
            if (S1 == null || S2 == null) {
                if (S1 == null) return S2 == null ? 0 : S2.length();
                else return S1 == null ? 0 : S1.length();
            }
            char max1 = S1.charAt(0), max2 = S2.charAt(0);
            Map<Character, Integer> map1 = new HashMap<>();
            for (int i = 0; i < S1.length(); i++) {
                char c = S1.charAt(i);
                if (map1.containsKey(c)) {
                    map1.put(c, map1.get(c) + 1);
                } else map1.put(c, 1);
                if (map1.get(c) > map1.get(max1)) max1 = c;
            }

            Map<Character, Integer> map2 = new HashMap<>();
            for (int i = 0; i < S2.length(); i++) {
                char c = S2.charAt(i);
                if (map2.containsKey(c)) {
                    map2.put(c, map2.get(c) + 1);
                } else map2.put(c, 1);
                if (map2.get(c) > map2.get(max2)) max2 = c;
            }
            // System.out.println(map1 + "   " + map2);

           S1 = S1.replace(max1, max2);
            System.out.println(S1 + "    " +  S2);
            int count  = 0;
            for (int i = 0; i < S1.length(); i++) {
                if (S1.charAt(i) != S2.charAt(i)) {
                    count++;
                }
            }
            return count;
        }

        public int GetMinDistance2 (String S1, String S2) {
            int len;
            if (S1 == null || (len = S1.length()) == 0) return 0;
            int[][] dic = new int[26][26]; //用来存储两者字符组合的个数， 如 s1 s2相同位置为ab的组合共有dic[0][1]个（每出现一次，dic[0][1] + 1)
            
            int m, n;
            for (int i = 0; i < 26; i++) {
               dic[S1.charAt(i) - 'a'][S2.charAt(i) - 'a'] += 1;//这个字符在字母表中的位置
            }

            int max = Integer.MIN_VALUE, count = 0;
            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    if (i == j) {
                        count += dic[i][j];
                    } else {
                        //当前位置是字符不相等的组合
                        //首先将S1的所有这个字符全部变成对方S2的那个字符
                        int change = dic[i][j] - dic[i][i];
                        //检查能否使得count取得***最大值*** 
                        max = Math.max(max, change);
                    }
                }
            }
            return S1.length() - max - count;
        }
        /* 

            对A大B小的概率，取差值分别28到25都会有一些结果。
            我将这几种差值分别放到了不同的结果表里面。
            但是对于A小B大的情况，我一一尝试了从20%到30%各种差值，都没有结果。
        
        */

        public int GetMinDistance (String S1, String S2) {
            int max = 0, count = 0, len = S1.length();
            int[][] dic = new int[26][26];
            char c1, c2;

            //将两个字符串字符映射到一个二维数组【只记录小写字母】
            for (int i = 0; i < len; i++) {
                c1 = S1.charAt(i);
                c2 = S2.charAt(i);
                dic[c1 - 'a'][c2 - 'a']++;
                if (c1 == c2) count++; //记录相同字符的数量
            } 

            for (int i = 0; i < 26; i++) {
                for (int j = 0; j < 26; j++) {
                    if (i != j) {
                        //尝试将i字符转为j字符，查看由此转化而出的相同数量能不能大于之前这样做的数量
                        int t = dic[i][j] + count - dic[i][i];//因为将i字符转为j字符，因此之前因为同是i字符产生的count需要除去

                        if (t > max) {
                            max = t;
                        }
                    }
                }
            }
            return len - max;
        }

        public static void main(String[] args) {
            Solution s = new Solution();
            // int res = s.GetMinDistance("aaaa", "bbbb");
            // int res = s.GetMinDistance("aabb","caef");
            int res = s.GetMinDistance("dlqaeopeekqbovglocneojijqyyusjvqcvwtmvqtlvyolfbekp","ruwhgprgrpvvdnprhtyvprligsgiyeysvdfmcywkragwxmakhd");

            System.out.println(res);
        }
    }
}
